package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

import java.util.*;

/**
 * @author jiazhaoxin
 * @Date 2022/2/24
 * @Desc
 */
public class 链表中下一个最大的节点 {


    @Test
    public  void  test(){
        int[] ints = nextLargerNodes(ListNode.build(1, 7, 5, 1, 9, 2, 5, 1));
        System.out.println("ints = " + ints);
    }

    public int[] nextLargerNodes(ListNode head) {
        List<Integer> result = new ArrayList();
        Stack<Integer> stack = new Stack();
        ListNode indexNode = head;
        int index = 0;
        while(indexNode!=null){
            int val = indexNode.val;
            while(!stack.isEmpty() && result.get(stack.peek())<val){
                result.set(stack.pop(),val);
            }
            result.add(val);
            stack.add(index);
            index++;
            indexNode = indexNode.next;
        }
        while(!stack.isEmpty()){
            result.set(stack.pop(),0);
        }
        return result.stream().mapToInt(Integer::intValue).toArray();

    }
}
